var lowestCommonAncestor = function (root, p, q) {
    function dfs(node) {
        if (!node) return null; // 递归出口
        if (node === p || node === q) return node; // 说明找到了p或q，将当前节点返回上去
        let left = dfs(node.left); // 递归遍历左子树
        let right = dfs(node.right); // 递归遍历右子树
        if (left !== null && right !== null) { // 当前节点左子树和右子树返回的都不为空，说明当前节点是公共祖先节点，返回上去
            return node
        }
        if (left === null && right !== null) { // 右不为空，说明右节点找到了目标
            return right
        } else if (left !== null && right === null) { // 左不为空，说明左节点找到了目标
            return left
        } else {
            return null // 左右都为空，当前节点不是祖先节点
        }
    }
    return dfs(root)
};

var lowestCommonAncestor = function (root, p, q) {
    function dfs(node) {
        if (!node) return null;
        if (node === p || node === q) return node;

        let left = dfs(node.left);
        let right = dfs(node.right);

        if (left !== null && right !== null) {
            return node;
        }
    }

    dfs(root);
}